﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 벨만-포드 알고리즘. 그래프의 최단경로를 구함
    /// 하나의 시작노드로 부터 모든 노드로의 최단경로를 구함
    /// 가중치는 음의 값일 수 있음
    /// O(V*E)
    /// </summary>
    class Bellman_Ford
    {
        private Edge[] es; //변
        private int[] d; //최단거리
        int V, E;

        /// <summary>
        /// 생성자
        /// </summary>
        /// <param name="maxSize">변 집합</param>
        /// <param name="es"></param>
        public Bellman_Ford(Edge[] es, int V, int E)
        {
            this.V = V;
            this.E = E;
            this.es = es;
            d = new int[V + 1];
        }

        /// <summary>
        /// s로 부터 모든 정점으로의 최단거리를 구함
        /// </summary>
        /// <param name="s"></param>
        public int[] ShortestPath(int s)
        {
            for (int i = 1; i <= V; i++)
            {
                d[i] = int.MaxValue;
            }
            d[s] = 0;
            bool update = true;
            while (update)
            {
                update = false;
                for (int i = 0; i < E; i++)
                {
                    Edge e = es[i];
                    if (d[e.From] != int.MaxValue && d[e.To] > d[e.From] + e.Cost)
                    {
                        d[e.To] = d[e.From] + e.Cost;
                        update = true;
                    }
                }
            }
            return d;
        }
    }
}
